import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    static {
        Solution test = new Solution();
        String[] words = new String[]{"a"};
        String s = "a";
        for(int i = 0; i <= 500; i++) {
            test.findSubstring(s, words);
        }
    }
    public List<Integer> findSubstring(String s, String[] words) {
        /**
         * 串联所有单词的子串
         * */
        // 1 预处理
        // -待处理字符串长度
        int n = s.length();
        // -单位元素长度
        int m = words[0].length();
        int len = words.length;
        // -创建目标字符串map
        Map<String, Integer> target = new HashMap<>();
        for(String str: words) {
            if(target.containsKey(str)) {
                target.put(str, target.get(str) + 1);
            } else {
                target.put(str, 1);
            }
        }
        // -创建返回数组
        List<Integer> retArray = new ArrayList<>();

        // 2 循环滑动
        for(int i = 0; i < m; i++) {
            // -单次滑动（固定窗口）
            int left = i;
            int right = i;
            Map<String, Integer> cur = new HashMap<>();
            while(right+m <= n) {
                // - 1,进窗口
                String tempStr = s.substring(right, right+m);
                if(cur.containsKey(tempStr)) {
                    cur.put(tempStr, cur.get(tempStr) + 1);
                } else {
                    cur.put(tempStr, 1);
                }

                // - 2,判断
                // notes:此处不使用right - left + 1，是因为right += m，而m是一个单调长度，此时right就是第二个单位的起点了
                if(right - left == m * (len - 1)) {
                    if(target.equals(cur)) {
                        retArray.add(left);
                    }
                    // - 3,出窗口
                    String popStr = s.substring(left, left + m);
                    cur.put(popStr, cur.get(popStr) - 1);
                    if(cur.get(popStr) == 0) {
                        cur.remove(popStr);
                    }
                    left += m;
                }

                right += m;
            }
        }

        // 3 返回值
        return retArray;
    }
}